今天的內容是來發一些刷題的時候常用的C++ code templates
致敬一下PoJen學長的Leetcode刷題pattern系列文章
不過學長的文章比較focus on pattern
也就是每個topic（像官神的github題目分類整理）都會有一些大致上的思路
但筆者今天這篇文章主要是focus on code templates
比較像是官神的github template整理
分成三部分
（應該要知道或是背起來）
累加
(對c++就是要打這麼長才能做到python sum做到的事情)
int sum = accumulate(v.begin(),v.end(),0);
取最值
int maxVal = *max_element(v.begin(),v.end());
轉換
string str = to_string(some_int);
int i = atoi(some_string);
float f = atof(some_other_string);
vector to set
set<int> s( vec.begin(), vec.end() );
set to vector
vector<int> newVec;
newVec.assign( s.begin(), s.end() );
(這兩個一起用拿來去重還蠻方便的)
custom compare
-> priority_queue:
auto comp = [](const SomeType& a, const SomeType& b) { return a.second > b.second; };
priority_queue< SomeType , vector<SomeType>, decltype(comp) > pq(comp)
->map:
auto comp = [](const SomeType& a, SomeType string& b) { return a.length() < b.length(); };
map<SomeType, SomeType, decltype(comp)> myMap(comp);
接下來是
在刷題刷到很熟練的時候常常會懶得打那麼多字
直接開自己的Google Keep把這些code貼上或是改一改來用
但雖然這樣偷懶的做法在比賽或是刷題的時候可以省一點點時間
但需要的時候筆者是可以直接一字不差的打出這些code的
千萬不要在還沒有刷題刷到熟練的時候就每次偷懶貼過去用
而且一要好好熟練跟理解這些template在做什麼
以免在面試的時候把最基本的一些東東打一打被面試官看到bug因此扣分
DSU
class DSU {
public:
DSU(int numOfNodes) {
n = numOfNodes;
par.resize(n);
iota(par.begin(), par.end(), 0); //assign 0 to n-1 to vector par
}
int find(int a){
if(par[a] == a) return a;
par[a] = find(par[a]); //path reduction
return par[a];
}
void join(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb) return;
par[pa] = par[pb] = min(pa,pb); //always choose min as parent
}
vector<int> par; //vector of parents
int n;
};
//usage:
DSU dsu(numOfNodes);
int parA = dsu.find(a);
dsu.join(a,b);
Trie
(LC 208的解答)
提到Trie就想要再提到一次不錯的變化題LC 677:https://leetcode.com/problems/map-sum-pairs/
class Trie {
public:
class TrieNode {
public:
array<TrieNode*,26> child;
bool isEnd;
};
Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(const string& word) {
TrieNode* cur = root;
for(char c: word){
if(cur->child[c-'a'] == nullptr){
cur->child[c-'a'] = new TrieNode();
}
cur = cur->child[c-'a'];
}
cur->isEnd = true;
}
/** Returns true if the word is in the trie. */
bool search(const string& word) {
TrieNode* cur = root;
for(char c: word){
if(cur->child[c-'a'] == nullptr){
return false;
}
cur = cur->child[c-'a'];
}
return cur->isEnd;
}
/** Returns true if there is any word in the trie that starts with the given prefix. */
bool startsWith(const string& prefix) {
TrieNode* cur = root;
for(char c: prefix){
if(cur->child[c-'a'] == nullptr){
return false;
}
cur = cur->child[c-'a'];
}
return true;
}
TrieNode* root;
};
//usage:
Trie t;
for(auto& w : words) t.insert(w);
BIT
class BIT {
public:
BIT(int n){
bit.resize(n+1); // bit is always 1-index.
}
int query(int idx){ // input parameter is 0-index for convenience
idx++;
int ans = 0;
while(idx){
ans += bit[idx];
idx -= idx & -idx;
}
return ans;
}
int query(int L, int R){ // [L,R], both ends are included
return query(R) - query(L-1);
}
void update(int idx, int val){ // input parameter is 0-index for convenience
int n = bit.size()-1;
idx++;
while(idx <= n){
bit[idx] += val;
idx += idx & -idx;
}
}
vector<int> bit;
};
//usage:
BIT bit(maxVal);
bit.update(idx /*use 0-index here*/, val);
bit.query(L,R);
Segment Tree
(說實話筆者覺得好像沒有哪一題是非得要用Segment Tree才能做的
雖然競賽的時候各式各樣的線段樹是基本常識，
個人認為對刷題和面試而言背熟線段樹的Template CP值不是很高）
需要的話請參考官神的線段樹template
https://github.com/wisdompeak/LeetCode/blob/master/Template/SegmentTree/range_sum.cpp
For 4-dir maze related problem
太多graph的題目會用到這個4-direction的for loop了特別提一下...
vector<pair<int,int>> dir{{1,0}, {-1,0}, {0,1}, {0,-1}};
for(auto& d: dir){
int nx = x + d.first;
int ny = y + d.second;
if(nx>=0 && ny>=0 && nx<m && ny<n /*通常還有 visit[nx][ny] == false*/){
}
}
在字串題，c++輸python輸最大的
（除了[a:b]的subscrpition)
就是沒有一個好用的split(delimiter) function了
好在有人幫各位打好這個function了
https://stackoverflow.com/questions/236129/how-do-i-iterate-over-the-words-of-a-string
vector<string> split (string& s, string& d) {
size_t pos_start = 0, pos_end, l = d.length();
string token;
vector<string> res;
while ((pos_end = s.find (delimiter, pos_start)) != string::npos) {
token = s.substr (pos_start, pos_end - pos_start);
pos_start = pos_end + l;
res.push_back(token);
}
res.push_back(s.substr (pos_start));
return res;
}
接下來就是
以面試會考的難度而言
比較套路一點的像是
Sliding Window/backtrack/Kadane/monotonic stack/topological sort/dijkstra/bfs等等等等
雖然好像都可以尻模板去改
但是就沒有向上面那些資料結構的重複性那麼高，
而且要打的code也沒那麼長，打完改完幾乎就是題目的解答
（就算是很套路的題目，也應該要可以自己把整個演算法的大框架現場寫出來）
基本上不應該需要整理模板尻上來改
筆者就不附錄其他的整理，只放最基本最簡單的binary search模板
（因為labuladong放的模板超難用，害我當初搞混很久Orz）
Binary Search for
LC 34. Find First and Last Position of Element in Sorted Array
(套用官神模板）
int n = nums.size();
//找左界
int L = 0, R = n-1;
while(L<R){
int mid = L + (R-L)/2;
if(nums[mid] >= target){
R = mid;
}else{
L = mid+1;
}
}
//跳出迴圈的時候 L==R, nums[L] != target就是沒找到
//找右界
L = 0; R = n-1;
while(L<R){
int mid = R - (R-L)/2;
if(nums[mid] <= target){
L = mid;
}else{
R = mid-1;
}
}
//跳出迴圈的時候 L==R, nums[L] != target就是沒找到
Sliding Window可以參考
https://leetcode.com/problems/frequency-of-the-most-frequent-element/discuss/1175088/C++-Maximum-Sliding-Window-Cheatsheet-Template!
iThome鐵人賽
看影片追技術